package com.yangli.leecode.mashib.code;

import java.util.HashMap;
import java.util.List;
import java.util.Stack;

/**
 * @Description
 * @Author liyang
 * @Date 2023/5/19 15:14
 */
// 课上讲的并查集实现
// 请务必看补充的Code06_UnionFind
// 那是数组实现的并查集，并且有测试链接
// 可以直接通过
// 这个文件的并查集是用map实现的
// 但是笔试或者平时用的并查集一律用数组实现
// 所以Code06_UnionFind更具实战意义
// 一定要看！
public class Code05_UnionFind  {
    // 课上讲的时候
    // 包了一层
    // 其实不用包一层哦
    public static class UnionFind<V> {
        public HashMap<V, V> father;
        public HashMap<V, Integer> size;//某个根节点下面拥有子节点数量

        public UnionFind(List<V> values) {
            father = new HashMap<>();
            size = new HashMap<>();
            for (V cur : values) {
                father.put(cur, cur);
                size.put(cur, 1);
            }
        }

        // 给你一个节点，请你往上到不能再往上，把代表返回
        public V findFather(V cur) {
            Stack<V> path = new Stack<>();
            while (cur != father.get(cur)) {
                path.push(cur);
                cur = father.get(cur);
            }
            while (!path.isEmpty()) {
                father.put(path.pop(), cur);
            }
            return cur;
        }

        public boolean isSameSet(V a, V b) {
            return findFather(a) == findFather(b);
        }

        public void union(V a, V b) {
            V aFather = findFather(a);
            V bFather = findFather(b);
            if (aFather != bFather) {
                int aSize = size.get(aFather);
                int bSize = size.get(bFather);
                if (aSize >= bSize) {
                    father.put(bFather, aFather);
                    size.put(aFather, aSize + bSize);
                    size.remove(bFather);
                } else {
                    father.put(aFather, bFather);
                    size.put(bFather, aSize + bSize);
                    size.remove(aFather);
                }
            }
        }

        public int sets() {
            return size.size();
        }

    }

}
